package com.company;

public class Searching {
    public static Comparable linearSearch (Comparable[] data, Comparable target)
    {
        Comparable result = null;
        int index = 0;

        while (result == null && index < data.length)
        {
            if (data[index].compareTo(target) == 0)
                result = data[index];
            index++;
        }

        return result;
    }


    public static Comparable binarySearch (Comparable[] data, Comparable target)
    {
        Comparable result = null;
        int first = 0, last = data.length-1, mid;

        while (result == null && first <= last)
        {
            mid = (first + last) / 2;  // determine midpoint
            if (data[mid].compareTo(target) == 0)
                result = data[mid];
            else
            if (data[mid].compareTo(target) > 0)
                last = mid - 1;
            else
                first = mid + 1;
        }

        return result;
    }

    //递归实现二分查找
    public static int binarySearch (int data[],int min, int max, int key)
    {
        int find = 85;
        int mid = (min + max) / 2;

        if (data[mid] == key)
            find= data[mid];

        else if (data[mid] > key)
        {
            if (min <= mid - 1)
                find = binarySearch(data, min, mid - 1, key);
        }

        else if (mid + 1 <= max)
            find = binarySearch(data, mid + 1, max, key);

        return find;
    }
}
